package 前缀和;

import java.util.HashMap;
import java.util.Map;

public class 连续数组7 {
    //https://leetcode.cn/problems/contiguous-array/description/
    public int findMaxLength1(int[] nums) {
        for (int i = 0; i <nums.length ; i++)
            if(nums[i] == 0) nums[i] = -1;
        Map<Integer,Integer> map = new HashMap<>(); // 存 前缀和及对应的下标
        int sum = 0, max_len = 0;
//        map.put(0,1);
//        for (int i : nums) {
//            sum += i;
//            ret += map.getOrDefault(sum - 0,0); // 找满足的前缀和
//            map.put(sum,map.getOrDefault(sum,0) + 1); // 存前缀和
//        }
//        return ret;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if(sum == 0) { // 如果当前遍历的前缀和为0，整个区间就是结果，往前翻不出此结果的，且此时一定是当前最长的
                max_len = i + 1;
                continue;
            }
            int dext = map.getOrDefault(sum - 0,i);
            int len = i - dext;
            max_len = Math.max(max_len,len);
            if(!map.containsKey(sum)) map.put(sum,i); // 应该保留前面已出现的 会更短的
        }
        return max_len;
    }
    public int findMaxLength(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,-1); // 默认存在一个前缀和为0的情况，前缀和为0的首默认情况，它是结果，个数(0,1)有一个结果、下标(0,-1)在-1下标有结果
        int sum = 0, ret = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += (nums[i] == 0 ? -1 : 1);
            if(map.containsKey(sum)) ret = Math.max(ret,i - map.get(sum));
            else map.put(sum,i);
        }
        return ret;
    }
}
